1. Field of the Invention
The present invention relates to a Wireless Sensor Network (WSN), and more particularly to a method for constructing a virtual backbone in consideration of link quality in a WSN.
2. Description of the Related Art
An ad-hoc network conventionally refers to a network structure in which all nodes mutually construct a network in an equal position without any difference in control functions or logical layers, and communicate with one another. Because the ad-hoc network does not use an existing backbone network, and has a limited transmission range, it employs multi-hop communications to reach all the devices or nodes in the network. Hence, each node is not only a host, but also operates as a router. As there is no limitation on an object for which a communication link is constructed, it is possible to configure a flexible network.
The technological evolution of a wireless ad-hoc network as described above has provided the technological foundation of various applications, such as a Wireless Sensor Network (WSN), a Wireless Mesh Network (WMN) (reference. IEEE 802.15.4 Specification, 2003), and the like. The WSN and the WMN show technological differentiation from other wireless data communications networks (i.e., infrastructure), in that a node is arbitrarily arranged over the WSN and the WMN simultaneously performs a role of a host and a role of a router. It is expected that demand for the WSN and the WMN continues to increase even henceforth, due to the development and the advantage of an aspect of cost efficiency in various wireless data communication arts, such as Zigbee, Radio Frequency IDentification (RFID), Ultra Wide Band (UWB), Worldwide interoperability for Microwave Access (WiMAX), and so on.
However, a broadcast storm phenomenon can occur in such networks due to causes including a failure of a network device, creation of a loop across the overall network, and the like. If the broadcast storm occurs, since the overall bandwidth of the network achieves a saturation state, the network can be faced with an inoperable state. To relieve the broadcast storm problem, and to improve the efficiency of the overall network, there is a method for constructing a virtual backbone.
The virtual backbone has been presented as a method for solving the broadcast storm problem which occurs in the WSN and in the WMN (reference: S.-Y. Ni, Y.-C. Tseng, T.-S. Chen, and J.-P. Sheu, “The Broadcasting Storm Problem in Mobile Ad-hoc Network, MOBIle COMputing Network (MOBICOM)”, pp. 151-162, August 1999), and has the value which can be reused as routing and a backup route in a network. As a method for constructing the virtual backbone, a method called a “Connected Dominating (or Dominator) Set (CDS)” has been proposed, and this approach can be called the same method as the cluster formation of a network topology (reference: S.-Y. Ni, Y.-C. Tseng, T.-S. Chen, and J.-P. Sheu, “The Broadcasting Storm Problem in Mobile Ad-hoc Network, MOBIle COMputing Network (MOBICOM)”, pp. 151-162, August 1999).
FIG. 1 is an exemplary view illustrating a backbone in a wireless ad-hoc network, and shows examples related to the construction of a virtual backbone and a CDS in the wireless ad-hoc network. To describe a concept of the virtual backbone, let us define some terms.                a neighbor node: A neighbor node indicates any node which is placed within a transmission range from a node.        U: a set of all nodes which are placed within a network        a CDS: a Connected Dominating Set        N[i]: a set of neighbor nodes and a node itself at a node i        a virtual backbone: when ∪ N[s]=U, and ∀s ∈ CDS, it is determined that a virtual backbone is successfully constructed. Any node in a CDS can reach (i.e., communicate with) another node through the CDS.        
With reference to FIG. 1, the wireless ad-hoc network has a form in which multiple mobile nodes 120 are connected to one another via multiple wireless links 140, and as described above, includes back nodes 130, each of which is formed by a set of dominator nodes and has the transmission range 110 of only each backbone node. As illustrated in FIG. 1, configuring the virtual backbone corresponds to a task of constructing a topology of a network, and FIG. 1 shows an example of the configuration of the virtual backbone using a concept of CDS. Methods for configuring a CDS in various formats have been proposed.
An approach which has been proposed in the incipient stage of CDS research, corresponds to a scheme of configuring a CDS on the premise that a topology of the overall network has already been known. A third scheme corresponds to a method in which information that is 2-hops away from the respective nodes is used. The latest approach describes a method for configuring a CDS by using only localized information, i.e. 1-hop away information. Basically, the configuration of an optimal CDS corresponds to a problem of Non-deterministic Polynomial-time hard (NP-hard), and the abovementioned methods correspond to heuristic approaches in which their respective properties are utilized. Fundamentally, since an assumption that a topology of the overall network can be known is not suitable in a Mobile Ad-hoc NETwork (MANET), a detailed description of this will be omitted.
A Core Extraction Distributed Ad-hoc Routing (CEDAR) protocol configures the CDS, exchanging information on dominators, the number of neighbor nodes, the number of neighbor nodes which select themselves as dominators, etc., through a beacon. By the selection of neighbor nodes, an individual node can be converted into a dominator.
A method which has been proposed (see J. Wu, “Extended Dominating-set-based Routing in Ad-hoc Wireless Networks with Unidirectional Links, IEEE Transaction on Parallel and Distributed Computing”, 22, 1-4, pp. 327-340, 2002) corresponds to a two-step process. In the first step, by using a marking process, an initial CDS is configured. In the second step, each node exchanges its neighbor list with its neighbor nodes. In this method, if all neighbor nodes of each node are included in a union of neighbor nodes of two neighbor nodes connected in a pair wise direction, each node removes itself from the initial CDS. The above method sets a goal of configuring a minimal CDS by using a heuristic approach like this.
B. Kim, J. Yang, D. Zhou, and M.-T. Sun, “Energy-aware Connected Dominating Set Construction in Mobile Ad-hoc Networks”, Fourteenth International Conference on Computer Communications and Networks (ICCN 2005), San Diego, Calif., October 2005, disclosed technology that sets a goal of configuring a minimal CDS by using a timer.
Meanwhile, in a mobile network, a Media Access Control (MAC) protocol which enables wireless hosts to efficiently share each wireless channel is required, and this scheme should be accomplished in a distributed manner. A Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) protocol corresponds to a distributed MAC protocol, and is being variously used at present.
FIG. 2 is timing diagram illustrating a transmission operation of each node according to the elapse of time in a CSMA/CA scheme. With reference to FIG. 2, in the CSMA/CA scheme, let us look around how a timer is used. An MAC protocol employing the CSMA/CA scheme uses a Automatic Repeat reQuest (ARQ) scheme which enables an acknowledgement responding to transmitted data to be received within a limited time so as to guarantee reliable communications during the transmission of frames.
Referring to FIG. 2, a sender waits for a time interval of a Dcf Inter-Frame Space (DIFS) 210, and then transmits a Request To Send (RTS) 220. If a receiver is ready for reception, it waits by a time interval of a Short Inter-Frame Space (SIFS) 230, and then transmits a Clear To Send 240 to give an answer. The sender waits for the SIFS 230, and then transmits data 250. On receiving the data 250, the receiver waits for the SIFS 230, and then gives an answer with an Acknowledgement (ACK) 260.
In the MAC protocol employing the CSMA/CA scheme, a station which desires to transmit frames first senses the state of a channel. If it is determined that the channel is in an idle state, (i.e., the channel is not used by another station) the station transmits frames. If it is a busy state, in which the channel is used by another station, the station defers the transmission of the frames during some time interval, and then retries the transmission. In the case of a busy state in this manner, a process of deferring the transmission of frames is referred to as a back-off process, and a time interval for which the transmission of frames is to be deferred is randomly determined at an instant when the station proceeds to the back-off process. The time interval is called back-off time. That is, when another station finishes using the channel, after the station checks that the channel is in an idle state during the DIFS period, in order to avoid a collision with still another station which is waiting for the transmission of frames, the station sets its back-off time by a back-off timer 270, and if the value of the back-off timer 270 is reduced to become ‘0’, then the station can transmit data. In fact, before a relevant station transmits frames, it is not only deterred for the back-off time, but is also additionally deterred by a time interval for which the channel is in a busy state while the station is in the back-off process. Namely, after a relevant station initially sets its back-off time by the back-off timer 270 when it enters the back-off process, it continues to reduce the value of the back-off timer 270 only if the channel is in an idle state. If the value of the back-off timer 270 becomes ‘0’, the relevant station transmits the frames. Hence, while the relevant station reduces the value of the back-off timer 270, determining that the channel is in an idle state, if the channel enters a busy state again, the relevant station stops the back-off timer 270, and then waits. If the channel enters an idle state again, the relevant station continues to reduce the value of the back-off timer 270 again.
Also, the CSMA/CA scheme adopts control packets, such as the RTS 220, the CTS 240, and the like, which enables each station to reserve a period of time for which each station uses a channel and to inform its neighbor stations of the relevant period of time, and inhibits another station from using transmission media during this period of time, thereby reducing the possibility of a collision among stations in a wireless channel.
The back-off timer 270 which corresponds to a timer used as a method for avoiding a collision between packets can be regarded as a defer timer, and is employed so as to avoid traffic congestion during the retransmission of packets. By using this concept, which is described in B. Kim, J. Yang, D. Zhou, and M.-T. Sun, “Energy-aware Connected Dominating Set Construction in Mobile Ad-hoc Networks”, Fourteenth International Conference on Computer Communications and Networks (ICCN 2005), San Diego, Calif., October 2005, the configuration of a CDS is disclosed, and the result approximating a minimal CDS is obtained.
The construction of an existing CDS is implemented, setting a goal of configuring a minimal CDS, and its approach also doesn't consider the efficiency of the overall network due to using a unit-disc approach. In a mesh network of a WSN, since communications among sensors can be frequently accomplished for a short period of time, it is required to configure a backbone in consideration of a plan which efficiently meets this. The existing method for utilizing a timer is designed to select only the shortest path by merely selecting a distant neighbor node. In the mesh network of the WSN, because the shortest path doesn't ensure a better link quality, in configuring the CDS by using a timer, a method for constructing a backbone by considering signal quality and interference is required.